/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.solr.util.hll;

import static com.carrotsearch.randomizedtesting.RandomizedTest.randomLong;

import com.carrotsearch.hppc.LongHashSet;
import java.util.HashSet;
import org.apache.solr.SolrTestCase;
import org.junit.Test;

/** Tests {@link HLL} of type {@link HLLType#EXPLICIT}. */
public class ExplicitHLLTest extends SolrTestCase {
  /** Tests basic set semantics of {@link HLL#addRaw(long)}. */
  @Test
  public void addBasicTest() {
    { // Adding a single positive value to an empty set should work.
      final HLL hll = newHLL(128 /*arbitrary*/);
      hll.addRaw(1L /*positive*/);
      assertEquals(hll.cardinality(), 1L);
    }
    { // Adding a single negative value to an empty set should work.
      final HLL hll = newHLL(128 /*arbitrary*/);
      hll.addRaw(-1L /*negative*/);
      assertEquals(hll.cardinality(), 1L);
    }
    { // Adding a duplicate value to a set should be a no-op.
      final HLL hll = newHLL(128 /*arbitrary*/);
      hll.addRaw(1L /*positive*/);
      assertEquals(hll.cardinality(), 1L /*arbitrary*/);
      assertEquals(hll.cardinality(), 1L /*dupe*/);
    }
  }

  // ------------------------------------------------------------------------
  /** Tests {@link HLL#union(HLL)}. */
  @Test
  public void unionTest() {
    { // Union of two distinct sets should work
      final HLL hllA = newHLL(128 /*arbitrary*/);
      final HLL hllB = newHLL(128 /*arbitrary*/);
      hllA.addRaw(1L);
      hllA.addRaw(2L);
      hllB.addRaw(3L);

      hllA.union(hllB);
      assertEquals(hllA.cardinality(), 3);
    }
    { // Union of two sets whose union doesn't exceed the cardinality cap should not promote
      final HLL hllA = newHLL(128 /*arbitrary*/);
      final HLL hllB = newHLL(128 /*arbitrary*/);
      hllA.addRaw(1L);
      hllA.addRaw(2L);
      hllB.addRaw(1L);

      hllA.union(hllB);
      assertEquals(hllA.cardinality(), 2);
    }
    { // Union of two sets whose union exceeds the cardinality cap should promote
      final HLL hllA = newHLL(128 /*arbitrary*/);
      final HLL hllB = newHLL(128 /*arbitrary*/);

      // fill up sets to explicitThreshold
      for (long i = 0; i < 128 /*explicitThreshold*/; i++) {
        hllA.addRaw(i);
        hllB.addRaw(i + 128);
      }

      hllA.union(hllB);
      assertEquals(hllA.getType(), HLLType.SPARSE);
    }
  }

  // ------------------------------------------------------------------------
  /** Tests {@link HLL#clear()} */
  @Test
  public void clearTest() {
    final HLL hll = newHLL(128 /*arbitrary*/);
    hll.addRaw(1L);
    assertEquals(hll.cardinality(), 1L);
    hll.clear();
    assertEquals(hll.cardinality(), 0L);
  }

  // ------------------------------------------------------------------------
  /** */
  @Test
  public void toFromBytesTest() {
    final ISchemaVersion schemaVersion = SerializationUtil.DEFAULT_SCHEMA_VERSION;
    final HLLType type = HLLType.EXPLICIT;
    final int padding = schemaVersion.paddingBytes(type);
    final int bytesPerWord = 8;

    { // Should work on an empty set
      final HLL hll = newHLL(128 /*arbitrary*/);

      final byte[] bytes = hll.toBytes(schemaVersion);

      // assert output has correct byte length
      assertEquals(bytes.length, padding /*no elements, just padding*/);

      final HLL inHLL = HLL.fromBytes(bytes);

      assertElementsEqual(hll, inHLL);
    }
    { // Should work on a partially filled set
      final HLL hll = newHLL(128 /*arbitrary*/);

      for (int i = 0; i < 3; i++) {
        hll.addRaw(i);
      }

      final byte[] bytes = hll.toBytes(schemaVersion);

      // assert output has correct byte length
      assertEquals(bytes.length, padding + (bytesPerWord * 3 /*elements*/));

      final HLL inHLL = HLL.fromBytes(bytes);

      assertElementsEqual(hll, inHLL);
    }
    { // Should work on a full set
      final int explicitThreshold = 128;
      final HLL hll = newHLL(explicitThreshold);

      for (int i = 0; i < explicitThreshold; i++) {
        hll.addRaw(27 + i /*arbitrary*/);
      }

      final byte[] bytes = hll.toBytes(schemaVersion);

      // assert output has correct byte length
      assertEquals(bytes.length, padding + (bytesPerWord * explicitThreshold /*elements*/));

      final HLL inHLL = HLL.fromBytes(bytes);

      assertElementsEqual(hll, inHLL);
    }
  }

  // ------------------------------------------------------------------------
  /** Tests correctness against {@link java.util.HashSet}. */
  @Test
  public void randomValuesTest() {
    final int explicitThreshold = 4096;
    final HashSet<Long> canonical = new HashSet<>();
    final HLL hll = newHLL(explicitThreshold);

    for (int i = 0; i < explicitThreshold; i++) {
      long randomLong = randomLong();
      canonical.add(randomLong);
      hll.addRaw(randomLong);
    }
    final int canonicalCardinality = canonical.size();
    assertEquals(hll.cardinality(), canonicalCardinality);
  }

  // ------------------------------------------------------------------------
  /** Tests promotion to {@link HLLType#SPARSE} and {@link HLLType#FULL}. */
  @Test
  public void promotionTest() {
    { // locally scoped for sanity
      final int explicitThreshold = 128;
      final HLL hll =
          new HLL(
              11 /*log2m, unused*/,
              5 /*regwidth, unused*/,
              explicitThreshold,
              256 /*sparseThreshold*/,
              HLLType.EXPLICIT);

      for (int i = 0; i < explicitThreshold + 1; i++) {
        hll.addRaw(i);
      }
      assertEquals(hll.getType(), HLLType.SPARSE);
    }
    { // locally scoped for sanity
      final HLL hll =
          new HLL(
              11 /*log2m, unused*/,
              5 /*regwidth, unused*/,
              4 /*expthresh => explicitThreshold = 8*/,
              false /*sparseon*/,
              HLLType.EXPLICIT);

      for (int i = 0; i < 9 /* > explicitThreshold */; i++) {
        hll.addRaw(i);
      }
      assertEquals(hll.getType(), HLLType.FULL);
    }
  }

  // ************************************************************************
  // assertion helpers
  /** Asserts that values in both sets are exactly equal. */
  private static void assertElementsEqual(final HLL hllA, final HLL hllB) {
    final LongHashSet internalSetA = hllA.explicitStorage;
    final LongHashSet internalSetB = hllB.explicitStorage;

    assertEquals(internalSetA, internalSetB);
  }

  /**
   * Builds a {@link HLLType#EXPLICIT} {@link HLL} instance with the specified explicit threshold.
   *
   * @param explicitThreshold explicit threshold to use for the constructed {@link HLL}. This must
   *     be greater than zero.
   * @return a default-sized {@link HLLType#EXPLICIT} empty {@link HLL} instance. This will never be
   *     <code>null</code>.
   */
  private static HLL newHLL(final int explicitThreshold) {
    return new HLL(
        11 /*log2m, unused*/,
        5 /*regwidth, unused*/,
        explicitThreshold,
        256 /*sparseThreshold, arbitrary, unused*/,
        HLLType.EXPLICIT);
  }
}
